package Tree;

import org.junit.Test;

/**
 * @Classname JZ33二叉搜索树的后序遍历序列
 * @Description TODO
 * @Date 2023/2/21 21:54
 * @Created by xjl
 */
public class JZ33二叉搜索树的后序遍历序列 {

    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }

    boolean recur(int[] postorder, int i, int j) {
        if (i >= j) {
            return true;
        }
        int p = i;
        // 从左边开始找到第一个小于根的元素的值
        while (postorder[p] < postorder[j]) {
            p++;
        }
        int m = p;
        // 从左边开始找到第一个大于或者等于的元素的值
        while (postorder[p] > postorder[j]) {
            p++;
        }
        // 判断是否相同，同时分别去判断的子数组的结构是否满足
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }

    @Test
    public void test(){
        boolean b = verifyPostorder(new int[]{1, 3, 2, 6, 5});
    }
}
